Computer processors are well known and widely used for a variety of purposes. One application of computer processors is digital signal processing (DSP). Digital signal processing is concerned with the representation of signals by sequences of numbers or symbols and the processing of these signals. DSP has a wide variety of applications and its importance is evident in such fields as pattern recognition, radio communication, telecommunications, radar, biomedical engineering, and many others. For DSP, it is often required to perform complex matrix multiplication and real matrix multiplication.
For convenience, abbreviations and mathematical expressions are defined as they will be used in the following.
Numbers a, b, c, or in general x, can be in a real domain (x.epsilon.) ("real numbers") and in a complex domain (x.epsilon..Fourier.) ("complex numbers"). The real domain is a subdomain of the complex domain .Fourier. (.OR right..Fourier.) so that any real number x is also a complex number x. For convenience of distinction, complex numbers x are underscored, wherein real numbers are not underscored.
Real numbers x (x.epsilon.) such as e.g., a=5.2, b=-7.8, or c=-40.56 are combined by real multiplication (*) according to: EQU c=a*b (1)
Complex numbers x (x.epsilon..Fourier.), such as e.g., x=a, b, or c, are defined as pairs [Re(x), Im(x)] having a real part Re(x) and an imaginary part Im(x), wherein Re and Im are numbers in the real domain (Re, Im.epsilon.).
By complex multiplication (*), two complex numbers a and b are combined to c: EQU c=a*b (2)
Thereby, the real parts Re(a) and Re(b) of a and b and the imaginary parts Im(a) and Im(b) of a and b are combined to the real part Re(c) of c according to: EQU Re(c)=+Re(a)*Re(b)-Im(a)*Im(b) (3)
and combined to the imaginary part Im(c) of c according to: EQU Im(c)=+Re(a)*Im(b)+Im(a)*Re(b). (4)
For convenience, equations (3) and (4) are written by real factors f.sub.1, f.sub.2, f.sub.3, and f.sub.4 (f.epsilon.): EQU Re(c)=f.sub.1 +f.sub.2 (5)
with EQU f.sub.1 =+Re(a)*.sub.1 Re(b) (6) EQU f.sub.2 =-Im(a)*.sub.2 Im(b) (7) EQU Im(c)=f.sub.3 +f.sub.4 (8) PA1 with EQU f.sub.3 =+Re(a)*.sub.3 Im(b) (9) EQU f.sub.4 =+Im(a)*.sub.4 Re(b). (10) PA1 e.g., J real part row vectors EQU {Re(X)}.sub.V (i)={Re(x(i,1))Re(x(i,n))Re(x(i,N))}; (20) PA1 e.g., I real part column vectors EQU {Re(X)}.sub.V (j)={Re(x(1,j))Re(x(i,j))Re(x(I,j))}; (21) PA1 e.g., J imaginary part row vectors EQU {Im(X)}.sub.V (i)={Im(x(i,1))Im(x(i,n))Im(x(i,N))}; and (22) PA1 e.g., I imaginary part column vectors EQU {Im(X)}.sub.V (j)={Im(x(1,j))Im(x(i,j))Im(x(I,j))}; (23)
wherein subscripts 1-4 under the multiplication sign * (*.sub.1, *.sub.2, *.sub.3, and *.sub.4) are indices for 4 required multiplication operations. Real multiplication is a special case of complex multiplication wherein all Im are Im=0.
Pluralities of numbers (e.g., complex x or only real x) which are arranged in a one-dimensional plurality can be expressed by vectors {X}.sub.V with the subscript "V" for vector. In connection with vectors, numbers x are called vector elements and have at least one index, e.g., n=1 to N. Complex vector {X}.sub.V having complex x can be written as: EQU {X}.sub.V ={x(1)x(n)x(N)} (11)
or with real parts Re in a separate real part vector as: EQU {Re(X)}.sub.V ={Re(x(1))Re(x(n))Re(x(N))} (12)
and imaginary parts Im in a separate imaginary part vector as: EQU {Im(X)}.sub.V ={Im(x(1))Im(x(n))Im(x(N))} (13)
Real vectors {X}.sub.V having real x can be written as: EQU {X}.sub.V ={x(1)x(n)x(N)} (14)
Pluralities of numbers (e.g., complex x or only real x) can also be arranged in a two-dimensional plurality and expressed as matrices with rows and columns. Numbers x, here called matrix elements x, can have row indices (e.g., i=1 to I, or n=1 to N) and column indices (e.g., j=1 to J, or n=1 to N). For convenience, indices are written in the order (row index, column index). The terms "row" and "column" are convenient abbreviations indicating a first and a second arrangement dimension. For example, complex matrix {X} has i=1 to I rows and j=1 to J columns: ##EQU1##
Matrix {X} has a number of e.g., I row vectors with each e.g., J elements x(i,j) with a common row index (e.g., i). For example, row vector {X}.sub.V (i) comprises elements x(i,j): EQU {X}.sub.V (i)={x(i,1) . . . x(i,j) . . . x(i,J)} (16)
Similarly, matrix {X} has a number of e.g., J column vectors of e.g., I elements x(i,j) with a common column index (e.g., j). For example, column vector {X}.sub.V (j) comprises elements x(i,j): EQU {X}.sub.V (j)={x(1,j)x(i,j)x(I,j)} (17)
For a complex matrix {X}, real parts Re(x) and imaginary parts Im(x) of matrix elements x can be considered separately. Matrix {X} has a real part matrix {Re(X)} and a imaginary part matrix {Im(X)}: EQU Re(x(1,1))Re(x(1,j))Re(x(1,J)) (18) EQU {Re(X)}=Re(x(i,1))Re(x(i,j))Re(x(i,J)) EQU Re(x(I,1))Re(x(I,j))Re(x(I,J)) EQU Im(x(1,1))Im(x(1,j))Im(x(1,J)) (19) EQU {Im(X)}=Im(x(i,1))Im(x(i,j))Im(x(i,J)) EQU Im(x(I,1))Im(x(I,j))Im(x(I,J))
In a vector classification, matrix {X} comprises
The multiplication of matrices is introduced with matrices {A}, {B}, and {C}. For example, matrix {A} has I*N matrix elements a(i,n) and matrix {B} has N*J matrix elements b(n,j). By complex matrix multiplication, matrices {A} and {B} are multiplied (*) according to: EQU {C}={A}*{B} (24)
or (25) ##EQU2## Elements c(i,j) in matrix {C} are calculated according to: ##EQU3## with * for complex multiplication as explained in equations (2) to (10). In other words, one element c(i,j) of matrix {C} is the so-called vector product (i,j) of row vector {A}.sub.V (i) of {A} and column vector {B}.sub.V (j): EQU c(i,j)={A}.sub.V (i)*{B}.sub.V (j) (27)
An operation such as in equation (27) is further referred to as vector multiplication.
For complex matrix multiplication, elements a(i,n) of {A} and b(n,j) of {B} are complex and equations (3) and (4) are used in equation (27). Real part Re(c(i,j)) and imaginary part Im(c(i,j)) of c(i,j) are calculated as: ##EQU4## In equations (28) and (29), the .SIGMA. symbol could also be placed in front of each *term, and the [ ] could then be left out.
Equations (28) and (29) can be expressed with f(i,j,n)-factors (similar to the f-factors of equations (6), (7), (9), and (10)) and intermediate results ReSum(i,j,n) and ImSum(i,j,n): ##EQU5## Using the vector classification of equations (20), (21), (22) and (23), matrix {C} is calculated as follows: Real part row vectors {Re(C)}.sub.V (i) are calculated when equation (30) is calculated for all j=1 to J. Imaginary part row vectors {Im(X)}.sub.V (i) are calculated when equation (31) is calculated for all j=1 to J.
By real matrix multiplication which is a special case of above mentioned complex matrix multiplication (24), (25), matrices {A} and {B} are multiplied (*) according to: EQU {C}={A}*{B} (32)
Thereby, elements a(i,n) and b(n,j) are real. Equation (26) for calculating one element c(i,j) is simplified to: ##EQU6## Equation (33) represents also scalar multiplication of row vector {A}.sub.V (i) and column vector {B}.sub.V (j). In other words, one element c(i,j) is the scalar product of row vector {A}.sub.V (i) of {A} and column vector {B}.sub.V (j) of {B}. A complete matrix {C} is calculated as follows: Row vectors {C}.sub.V (j) are obtained when equation (33) is calculated for j=1 to J.